package Solutions;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname IsValidBST
 * @Description TODO
 * @Date 2021/6/18 11:33
 * @Created by ASUS
 */
public class IsValidBST {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /***
     * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
     *
     * 假设一个二叉搜索树具有如下特征：
     *
     *     节点的左子树只包含小于当前节点的数。
     *     节点的右子树只包含大于当前节点的数。
     *     所有左子树和右子树自身必须也是二叉搜索树。
     *
     * 示例 1:
     *
     * 输入:
     *     2
     *    / \
     *   1   3
     * 输出: true
     *
     * 示例 2:
     *
     * 输入:
     *     5
     *    / \
     *   1   4
     *      / \
     *     3   6
     * 输出: false
     * 解释: 输入为: [5,1,4,null,null,3,6]。
     *      根节点的值为 5 ，但是其右子节点值为 4 。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    // 全局变量，如果不用此方法就要递归传参，但是比较麻烦
    // 这里一开始是boolean类型的，但是为了节省内存，换成了byte，用于判断是否该停止
    private static byte stop;
    // 记录前一个数的值，需要注意点是这里需要啥long类型，否则会在int边界值处出错
    private static long pre;
    public boolean isValidBST(TreeNode root) {
        // 参数判断
        if (root == null) return true;
        // 初始化
        stop = 0;
        pre = Long.MIN_VALUE;
        isValid(root);
        return stop == 0;
    }
    public void isValid(TreeNode root) {
        // stop可以提前结束
        if (root == null || stop == 1) return;
        // 看左子树是否合理
        isValid(root.left);
        // 发现不符合的时候，立刻停止遍历
        if (pre >= root.val) {
            stop = 1;
            return;
        }
        // 更新pre
        pre = root.val;
        // 看右子树是否合理
        isValid(root.right);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2,new TreeNode(1,null,null),new TreeNode(3,null,null));
        System.out.println(new IsValidBST().isValidBST(root));
    }

    /***
     * 执行结果：
     * 通过
     * 显示详情
     *
     * 添加备注
     * 执行用时：2 ms, 在所有 Java 提交中击败了27.48% 的用户
     * 内存消耗：38.2 MB, 在所有 Java 提交中击败了18.05% 的用户
     */
    public boolean isValidBST_(TreeNode root) {
        if (root == null) return false;
        List<Integer> list = new ArrayList<>();
        query(root, list);
        long min = Long.MIN_VALUE;
        for (Integer integer : list) {
            if (integer <= min) return false;
            min = integer;
        }
        return true;
    }

    private void query(TreeNode root, List<Integer> list) {
        if (root == null) return;
        query(root.left, list);
        list.add(root.val);
        query(root.right, list);

    }


}
